package algorithm_diagram;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//选择排序：使用最小排除法对数组进行排序，花费n^2时间
//创建一个数组，假设索引0为最小，与每一位相比，拿到最小数的给新数组，将这一位的数从原数组中删除，再重复循环此步骤直到数组最后一位。
public class SelectionSort {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(34, 56, 23, 6, 87, 123, 999, 888, 345));
        System.out.println(selectionSort01(list));
        int[] arr = {34, 56, 23, 6, 87, 123, 999, 888, 345};
        System.out.println(Arrays.toString(selectionSort02(arr)));
    }

    //集合
    private static List<Integer> selectionSort01(List<Integer> list){
        int size = list.size();
        List<Integer> newList = new ArrayList<>(size);
        int smallestIndex=0;
        Integer smallest;
        for(int i=0;i<size;++i){
            int listSize = list.size();
            smallest=list.get(0);
            for(int j=0;j<listSize;++j){
                if(list.get(j)<=smallest){
                    smallest=list.get(j);
                    smallestIndex=j;
                }
            }
            newList.add(list.get(smallestIndex));
            list.remove(smallestIndex);
        }
        return newList;
    }

    //数组
    private static int[] selectionSort02(int[] arr){
        int[] newArr = new int[arr.length];
        for(int i=0;i<newArr.length;++i){
            int smallest=arr[0];
            int smallestIndex=0;
            for(int j=0;j<arr.length;++j){
                if(arr[j]<smallest){
                    smallest=arr[j];
                    smallestIndex=j;
                }
            }
            newArr[i]=arr[smallestIndex];
            int[] replaceArr=new int[arr.length-1];
            for(int p=0;p<arr.length;++p){
                if(p<smallestIndex){
                    replaceArr[p]=arr[p];
                }else if(p>smallestIndex){
                    replaceArr[p-1]=arr[p];
                }
            }
            arr=replaceArr;
        }
        return newArr;
    }
}
